package b_sorting_advance.c_heap_sort;

import utils.ArrayGeneric;
import utils.sorting_helper.SortingTest;

/**
 * @Author: DeLucia
 * @Description:
 * @Date: 2019/1/28 23:12.
 * <p>
 * 使用最大堆的思想进行排序
 * 1. 从最后一个非叶子节点 len - 1 / 2 对下标递减迭代进行 shiftDown 操作
 * 2. 将堆顶元素交换到末尾 直至完成排序过程
 */
@SuppressWarnings("unchecked")
public class HeapSorting extends SortingTest {


    @Override
    public void sort(ArrayGeneric arr) {
        heapSort(arr);
    }

    /**
     * 最大堆原地排序
     *
     * @param arr
     */
    private void heapSort(ArrayGeneric arr) {
        // heapipy
        // 从最后一个非叶子节点 len - 1 / 2 向上进行 shiftDown 操作
        int len = arr.length();
        for (int i = (len - 1) / 2; i >= 0; i--) {
            shiftDown(arr, len, i);
        }
        // shiftDown
        // 将堆顶元素交换到末尾 直至完成排序过程
        for (int i = len - 1; i > 0; i--) {
            arr.swap(0, i);
            shiftDown(arr, i, 0);
        }

    }

    /**
     * 向下转换 - 保持最大堆的性质
     *
     * @param arr 操作的数组
     * @param len 操作的数组的长度
     * @param k   发生交换的下标(shiftDown)
     */
    private void shiftDown(ArrayGeneric arr, int len, int k) {
        Comparable e = arr.get(k);
        while (2 * k + 1 < len) { // 交换对象预设成左孩子节点
            int j = 2 * k + 1; // 左孩子
            // 如果有孩子存在 && 右孩子 比 左孩子大 就将交换对象切换到右孩子
            if (j + 1 < len && arr.get(j + 1).compareTo(arr.get(j)) > 0) {
                j += 1;
            }
            // 如果待交换元素小于等于它最大的孩子就不需要进行交换了
            if (e.compareTo(arr.get(j)) >= 0) break;
            // 否则就交换
            arr.put(k, arr.get(j));
            // 被交换的元素作为下一个考察对象
            k = j;
        }
        arr.put(k, e);
    }
}
